﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace RoutingAlgorithms
{
    class Routing
    {
        private Topology map;

        private Dictionary<int, Node> nodes;

        // Use for prevent make change in map while processing
        private Dictionary<Link, double> usable_bw;

        public Topology Map
        {
            get { return map; }
            set { 
                map = value;
                foreach (Node node in map.Nodes)
                {
                    nodes[node.Id] = node;
                }
            }
        }

        public Routing()
        {
            map = new Topology();
            nodes = new Dictionary<int, Node>();
            usable_bw = new Dictionary<Link, double>();
        }

        public Routing(Topology map)
        {
            this.map = map;
            nodes = new Dictionary<int, Node>();
            usable_bw = new Dictionary<Link, double>();
            foreach (Node node in map.Nodes)
            {
                nodes[node.Id] = node;
                foreach (Link link in node.Links)
                {
                    usable_bw[link] = link.Capacity;
                }
            }
        }

        /*******************************************************************
         *  BFS
         *  
         *  CODER:  HOANG CHUNG HIEN
         *  DATE:   27/3/2013
         *  VERSION: 1.0
         *  
         *******************************************************************/
        public Path BFS(Node source, Node dest)
        {
            Path result_path = new Path();

            Node curNode; // use for browse map

            // queue use for browse from source node to find out dest node
            Queue<Node> queue = new Queue<Node>();

            // tracking use for record browsed link
            Stack<Link> tracking = new Stack<Link>();

            // found or not dest node
            bool found = false;

            // checked node
            Dictionary<Node, bool> checked_node = new Dictionary<Node, bool>();
            foreach (Node node in map.Nodes)
            {
                checked_node.Add(node, false);
            }

            // Add source node to queue
            queue.Enqueue(source);

            // Find out destination node..
            while (queue.Count > 0 && !found)
            {
                curNode = queue.Dequeue();
                foreach (Link link in curNode.Links)
                {
                    if (usable_bw[link] > 0 && !checked_node[link.Destination])
                    {
                        // Track this link
                        tracking.Push(link);

                        if (link.Destination == dest)
                        {
                            found = true;
                            break;
                        }
                        else
                        {
                            // Checked neighbor node
                            checked_node[link.Destination] = true;

                            // Add neighbor to queue
                            queue.Enqueue(link.Destination);
                        }
                    }
                }
            }

            // Get the invert path from tracking
            Link now = tracking.Pop();
            Stack<Link> temp = new Stack<Link>();
            temp.Push(now);
            Link next;

            while (tracking.Count > 0)
            {
                next = tracking.Pop();
                if (now.Source == next.Destination)
                {
                    now = next;
                    temp.Push(now);
                }
            }

            // Get the path from invert path in temp stack
            while (temp.Count > 0)
            {
                result_path.Links.Add(temp.Pop());
            }

            return result_path;
        }


        /*******************************************************************
         *  MHA (Minimum hop algorithm)
         *  
         *  CODER:  HOANG CHUNG HIEN
         *  DATE:   27/3/2013
         *  VERSION: 1.0
         *  
         *******************************************************************/
        public Path MHA(Request request)
        {
            double bw = request.Bandwidth;

            // Remove links with link.bandwidth less than request.bandwidh
            //   remove it by set usable_bw[link] = 0
            foreach (Node node in map.Nodes)
            {
                foreach (Link link in node.Links)
                {
                    if (bw > link.Bandwidth)
                        usable_bw[link] = 0;
                }
            }

            Path result = BFS(nodes[request.Source], nodes[request.Destination]);

            return result;
        }


        /*******************************************************************
         *  K SHORTEST PATH
         *  
         *  CODER:  HOANG CHUNG HIEN
         *  DATE:   12/3/2013
         *  VERSION: 1.0
         *  
         *******************************************************************/
        public static List<Path> K_Shortest_Path(Node source, Node dest)
        {
            // Result path
            List<Path> r_paths = new List<Path>();

            // Use while generate temporary tree node
            Dictionary<Node, List<Link>> Tree = new Dictionary<Node, List<Link>>();
            // Use for tracking visited node
            Dictionary<Node, bool> visited_node = new Dictionary<Node, bool>();
            // User for tracking visited link
            Dictionary<Link, bool> visited_link = new Dictionary<Link, bool>();

            //
            // Generate Tree by source & map
            //
            
            // Use while browse map
            Queue<Link> link_queue = new Queue<Link>();
            Dictionary<Node, int> node_father = new Dictionary<Node, int>();
            Dictionary<Node, int> node_level = new Dictionary<Node, int>();
            //
            // Initialize for process tree
            foreach(Node n in map.Nodes)
            {
                node_father[n] = -1;
                node_level[n] = int.MaxValue;
                Tree[n] = new List<Link>();
                visited_node[n] = false;
                foreach (Link l in n.Links)
                    visited_link[l] = false;
            }
            node_level[source] = 0;
            foreach (Link link in source.Links)
            {
                Tree[source].Add(link);
                link_queue.Enqueue(link);
                node_father[link.Destination] = source.Id ;
                node_level[link.Destination] = 0;
                visited_node[link.Destination] = true;
                visited_link[link] = true;
            }
            //
            // Process tree
            while (link_queue.Count > 0)
            {
                Link link = link_queue.Dequeue();
                foreach (Link l in link.Destination.Links)
                {
                    // If destination node isn't brother, and destination node isn't father node
                    // and destination node isn't brother of father
                    if (node_father[link.Destination] != node_father[l.Destination]
                        && l.Destination != link.Source 
                        && node_level[l.Destination] > node_level[link.Destination])
                    {
                        // If a link isn't added to Tree (or visited), add it and set visited is true
                        if (!visited_link[l])
                        {
                            Tree[link.Destination].Add(l);
                            visited_link[l] = true;
                        }
                        // Add information about node father for prevent go back link
                        node_father[l.Destination] = l.Source.Id;

                        // Tracking is a node visited
                        if (!visited_node[l.Destination])
                            node_level[l.Destination] = node_level[link.Destination] + 1;

                        link_queue.Enqueue(l);
                        //System.Threading.Thread.Sleep(1500);
                        //Console.WriteLine(node_father[l.Destination] + "-" + link.Source.ID);
                        //Console.WriteLine(l.Source.ID + "-" + l.Destination.ID);
                    }
                }
                if (!visited_node[link.Destination])
                    visited_node[link.Destination] = true;
                
                //Console.WriteLine(link.Source.ID + " : " + link.Destination.ID + "    L " + link.Destination.ID + " : " + 
                //    node_father[link.Destination]);
                //Console.WriteLine(node_father[link.Destination]);
            }
            
            //
            // Generate paths by Tree
            //
            
            // Use for deepth first search
            Stack<Link> link_stack = new Stack<Link>();
            //
            // Use for tracking a new path
            Stack<Link> temp_path = new Stack<Link>();

            //
            // Get first link from source node
            foreach (Link link in Tree[source])
            {
                link_stack.Push(link);
            }
            while (link_stack.Count > 0)
            {
                Link link = link_stack.Pop();

                // While a path found, go back by pop out link for store other path
                while (temp_path.Count > 0 && temp_path.Peek().Destination != link.Source)
                    temp_path.Pop();
                //
                // Continue to get new path
                temp_path.Push(link);
                foreach (Link l in Tree[link.Destination])
                {
                    link_stack.Push(l);
                }

                // If destination is found
                if (link.Destination == dest)
                {
                    //
                    // Create a new path for hold links
                    Path path = new Path();
                    // 
                    // Create a stack for get link from invert links
                    Stack<Link> temp = new Stack<Link>();
                    //
                    // Get invert link from temp_path
                    foreach (Link li in temp_path)
                    {
                        temp.Push(li);
                    }
                    //
                    // OK, now get path
                    while (temp.Count > 0)
                    {
                        Link l = temp.Pop();
                        path.Links.Add(l);
                    }
                    // Store it
                    r_paths.Add(path);

                }
            }

            return r_paths;
            //public Path 

        }



    }
}
